#define  _CRT_SECURE_NO_WARNINGS

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node* copyHead;
        Node* copyTail;
        copyHead = copyTail = nullptr;
        Node* cur = head;
        while (cur)
        {
            if (copyHead == nullptr)
            {
                copyHead = copyTail = new Node(cur->val);
            }
            else
            {
                copyTail->next = new Node(cur->val);
                copyTail = copyTail->next;
            }
            cur = cur->next;
        }

        map<Node*, Node*> nodeMap;
        Node* copy = copyHead;
        cur = head;
        while (cur)
        {
            nodeMap[cur] = copy;
            copy = copy->next;
            cur = cur->next;
        }

        cur = head, copy = copyHead;
        while (cur)
        {
            copy->random = nodeMap[cur->random];
            copy = copy->next;
            cur = cur->next;
        }

        return copyHead;
    }
};